English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Prawie szablon [A] (sza)
Quasi-template [A]
Memory limit: 192 MB
A template of a word 
is such a word 
that
all occurrences of 
within 
cover the whole word 
(i.e. each letter of the word 
appears within some fragment
of consecutive letters of 
equal to 
).
By quasi-template of a word 
we mean such a word
that 
is a substring (i.e. a fragment of consecutive letters) of 
and 
is a template of some superstring of 
. The figure below shows
why the word aabaa is a quasi-template of the word
aaaabaabaaaba:
For a given word 
we would like to compute the number of its
quasi-templates and the shortest one of them.
Input
The only line of the standard input contains a non-empty word 
that is not
longer than 
letters.
It consists of small letters of English alphabet.
Output
The first line of the standard output should contain the number of
quasi-templates of word 
.
The second line should contain the shortest word being a quasi-template of
word 
.
If there is more than one such shortest word, output the lexicographically
smallest from the shortest quasi-templates.
Example
For the input data:
aaaabaabaaaba
the correct result is:
10 aabaa
The word from the sample input has 10 quasi-templates: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, and abaabaaa.
Task author: Tomasz Idziaszek.